/*
 * @lc app=leetcode.cn id=473 lang=typescript
 *
 * [473] 火柴拼正方形
 */

// @lc code=start
function makesquare(matchsticks: number[]): boolean {
  const backtrack = (idx: number, arr: number[], matchsticks: number[]): boolean => {
    if (idx === -1) return true;
    for (let i = 0; i < 4; i++) {
      // 这条边放不下火柴
      if (arr[i] < matchsticks[idx]) continue;
      // 这条边能放下火柴或者这边的容量大于当前火柴数量加上最少的火柴数量
      if (arr[i] === matchsticks[idx] || arr[i] >= matchsticks[idx] + matchsticks[0]) {
        arr[i] -= matchsticks[idx];
        if (backtrack(idx - 1, arr, matchsticks)) return true;
        // 上面的选择无效，这里回溯回去，重新选择
        arr[i] += matchsticks[idx];
      }
    }
    return false;
  };
  let sum = 0;
  for (let n of matchsticks) {
    sum += n;
  }

  // 总数不够分成4条边
  if (sum % 4 !== 0) return false;
  matchsticks.sort((a, b) => a - b);
  const arr = new Array(4).fill(sum / 4);
  return backtrack(matchsticks.length - 1, arr, matchsticks);
}
// @lc code=end
